package com.ieslab.dynamicp;

import java.util.HashMap;
import java.util.Map;

/**
 * 资源分配问题
 */
public class ResourceAllocation {
	private static Map<Integer, String> gainMap = new HashMap<>();
	static {
		gainMap.put(1, "0,0.11,0.13,0.15,0.21,0.24,0.3,0.35");
		gainMap.put(2, "0,0.12,0.16,0.21,0.23,0.25,0.24,0.34");
		gainMap.put(3, "0,0.08,0.12,0.2,0.24,0.26,0.3,0.35");
	}

	public static void main(String[] args) {
		int projectCount = 3;
		int investmentAmount = 7;
		String[] inputStrs = gainMap.get(1).split(",");
		double[] q = new double[investmentAmount + 1]; // 存储原始数据
		double[] f = new double[investmentAmount + 1]; // 存储当前最大收益情况
		int[][] a = new int[projectCount + 1][investmentAmount + 1]; // 前k个工程投资j所获得的最大利润时，给第k个工程分配的资源数
		System.out.println("请输入第一个项目的收益表");
		int j = 0;
		for (j = 0; j <= investmentAmount; j++) {
			q[j] = Double.parseDouble(inputStrs[j]);
			f[j] = q[j];
		}
		for (j = 0; j <= investmentAmount; j++) {
			a[1][j] = j;
		}
		int k = 0;
		double[] temp = new double[investmentAmount + 1]; // 记录正在计算的最大收益
		int i = 0;
		for (k = 2; k <= projectCount; k++) {
			System.out.println("请输入第" + k + "个项目的收益表");
			inputStrs = gainMap.get(k).split(",");
			for (j = 0; j <= investmentAmount; j++) {
				temp[j] = q[j]; // gkq:暂存最大收益
				q[j] = Double.parseDouble(inputStrs[j]);
				// a[k][j] = 0; // gkq:初始化-java中可省略，因为默认初始值就是0
			}
			for (j = 0; j <= investmentAmount; j++) { // gkq:j是总投资额
				for (i = 0; i <= j; i++) {
					if (f[j - i] + q[i] > temp[j]) { // gkq:分段决策过程
						temp[j] = f[j - i] + q[i];
						a[k][j] = i; // gkq:前k个工程投资j所获得最大利润时，给第k个工程分配的投资额
					}
				}
			}
			for (j = 0; j <= investmentAmount; j++) {
				f[j] = temp[j];
			}
		}
		int rest = investmentAmount;
		int[] gain = new int[projectCount + 1];
		for (k = projectCount; k >= 1; k--) {
			gain[k] = a[k][rest];
			rest -= gain[k];
		}
		for (k = 1; k <= projectCount; k++) {
			System.out.println("分配给第" + k + "个项目的资源数：" + gain[k]);
		}
		System.out.println("最大收益f(" + investmentAmount + ")=" + f[investmentAmount]);
	}
}
